package exercises.newcoder.solution;

/**
 * <a href="https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac?tpId=188&&tqId=38644&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 *     NC127 最长公共子串</a>
 * @author or2
 * @Description 动态规划问题
 * @create 2021年08月30日 时间: 23:03
 */
public class LCS {
    /**
     * 最长公共子串
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        // write code here
        if (s1.isEmpty() || s2.isEmpty()) {
            return "";
        }

        int lengthS1 = s1.length();
        int lengthS2 = s2.length();
        int[][] dp = new int[lengthS1][lengthS2];

        int max = 0;
        int index = 0;

        for (int i = 0; i < lengthS1; i++) {
            for (int j = 0; j < lengthS2; j++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    dp[i][j] = i == 0 ? 1 : j == 0 ? 1 : 1 + dp[i - 1][j - 1];
                    if (dp[i][j] > max) {
                        max = dp[i][j];
                        index = i;
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }

//        字串函数不包含最后下标, 因此 + 1
        index++;
        return s1.substring(index - max, index);
    }

    public static void main(String[] args) {
        LCS lcs = new LCS();
        String s1 = "1A2C3D4B56";
        String s2 = "B1D23A456A";
        System.out.println(lcs.LCS(s1, s2));
    }
}